package LeetCode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.TreeMap;

public class WordLadder {

  public int ladderLength(String start, String end, HashSet dict) {
    Set set = new HashSet();
    Queue queue = new LinkedList();
    queue.offer(start);
    int distance = 1;
    int count = 1;
    set.add(start);

    while (count > 0) {
      while (count > 0) {
        char[] curr = ((String) queue.poll()).toCharArray();

        for (int i = 0; i < curr.length; i++) {
          char tmp = curr[i];
          for (char c = 'a'; c <= 'z'; c++) {
            if (c == tmp)
              continue;
            curr[i] = c;
            String str = new String(curr);
            if (str.equals(end))
              return distance + 1;
            if (dict.contains(str) && !set.contains(str)) {
              queue.offer(str);
              set.add(str);
            }
          }
          curr[i] = tmp;
        }
        count--;
      }
      distance++;
      count = queue.size();
    }
    return 0;
  }

  public static LinkedList<String> transform(String startWord, String stopWord,
      Set<String> dictionary) {
    startWord = startWord.toUpperCase();
    stopWord = stopWord.toUpperCase();
    Queue<String> actionQueue = new LinkedList<String>();
    Set<String> visitedSet = new HashSet<String>();
    Map<String, String> backtrackMap = new TreeMap<String, String>();

    actionQueue.add(startWord);
    visitedSet.add(startWord);

    while (!actionQueue.isEmpty()) {
      String w = actionQueue.poll();
      // For each possible word v from w with one edit operation
      for (String v : getOneEditWords(w)) {
        if (v.equals(stopWord)) {
          // Found our word! Now, back track.
          LinkedList<String> list = new LinkedList<String>();
          // Append v to list
          list.add(v);
          while (w != null) {
            list.add(0, w);
            w = backtrackMap.get(w);
          }
          return list;
        }

        // If v is a dictionary word
        if (dictionary.contains(v)) {
          if (!visitedSet.contains(v)) {
            actionQueue.add(v);
            visitedSet.add(v); // mark visited
            backtrackMap.put(v, w);
          }
        }
      }
    }
    return null;
  }

  private static Set<String> getOneEditWords(String word) {
    Set<String> words = new HashSet<String>();
    // for every letter
    for (int i = 0; i < word.length(); i++) {
      char[] wordArray = word.toCharArray();
      // change that letter to something else
      for (char c = 'A'; c <= 'Z'; c++) {
        if (c != word.charAt(i)) {
          wordArray[i] = c;
          words.add(new String(wordArray));
        }
      }
    }
    return words;
  }

  public static ArrayList<ArrayList<String>> wordLadderII(String start,
      String end, HashSet<String> dict) {
    ArrayList<ArrayList<String>> ret = new ArrayList<ArrayList<String>>();
    ArrayList<String> path = new ArrayList<String>();
    wordLadderIIHelper(start, end, dict, path, ret);

    int min = 0;
    for (ArrayList<String> item : ret) {
      min = min == 0 || item.size() < min ? min = item.size() : min;
    }

    for (int i = 0; i < ret.size(); i++) {
      if (ret.get(i).size() > min)
        ret.remove(i--); // REMEMBER the "i--" when removing elements from
                         // ArrayList
    }
    return ret;
  }

  public static void wordLadderIIHelper(String start, String end,
      HashSet<String> dict, ArrayList<String> path,
      ArrayList<ArrayList<String>> ret) {
    path.add(start);
    char[] sArr = start.toCharArray();
    for (int i = 0; i < sArr.length; i++) {
      char origin = sArr[i];
      for (char c = 'a'; c <= 'z'; c++) {
        if (c != origin) {
          sArr[i] = c;
          String temp = new String(sArr);
          if (temp.equals(end)) {
            path.add(temp);
            ret.add(new ArrayList<String>(path));
            path.remove(path.size() - 1);
          }
          if (dict.contains(temp) && !path.contains(temp))
            wordLadderIIHelper(temp, end, dict, path, ret);
        }
      }
      sArr[i] = origin;
    }
    path.remove(path.size() - 1);
  }


  /**
   * @param args
   */
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    WordLadder w = new WordLadder();
    HashSet<String> dict = new HashSet<String>();
    dict.add("hot");
    dict.add("dot");
    dict.add("dog");
    dict.add("lot");
    dict.add("log");
    dict.add("cog");
    dict.add("ceg");
    System.out.println(w.ladderLength("hot", "dog", dict));
  }

}
